894E - Ralph and Mushrooms - CodeForces Solution

#include<bits/stdc++.h>
struct edge{
	int nxt,to,val;
}v[1000005];
int head[1000005];
int dfn[1000005],low[1000005],tdx;
int scc_id[1000005],scc;
std::stack<int>S;
void tarjan(const int&p){
	dfn[p]=low[p]=++tdx;
	S.push(p);
	for(int i=head[p];i;i=v[i].nxt){
		if(!dfn[v[i].to]){
			tarjan(v[i].to);
			low[p]=std::min(low[p],low[v[i].to]);
		}else if(!scc_id[v[i].to])
			low[p]=std::min(low[p],dfn[v[i].to]);
	}
	if(dfn[p]==low[p]){
		++scc;
		while(!S.empty()){
			scc_id[S.top()]=scc;
			if(S.top()==p)break;
			S.pop();
		}
		S.pop();
	}
}
std::vector<std::pair<int,int> >g[1000005];
int in[1000005];
long long dp[1000005];
long long val[1000005];
int n;
void topo(int s){
	std::queue<int>q;
	for(int i=1;i<=scc;++i){
		if(!in[i])q.push(i);
		dp[i]=-1e18;
	}
	dp[s]=val[s];
	while(!q.empty()){
		int t1=q.front();q.pop();
		for(const auto&i:g[t1]){
			dp[i.first]=std::max(dp[i.first],dp[t1]+i.second+val[i.first]);
			if(!(--in[i.first]))q.push(i.first);
		}
	}
}
inline long long calc(int x){
	int t=sqrt((x<<1)+0.25)-0.5;
	return x+1ll*t*x-t*(t+1ll)*(t+2)/6;
}
int m;
long long ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		v[i]=(edge){head[x],y,z};
		head[x]=i;
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;++i){
		for(int j=head[i],x;j;j=v[j].nxt){
			if(scc_id[i]==scc_id[v[j].to])
				val[scc_id[i]]+=calc(v[j].val);
			else
				g[scc_id[i]].emplace_back(scc_id[v[j].to],v[j].val),++in[scc_id[v[j].to]];
		}
	}
	scanf("%d",&m);
	topo(scc_id[m]);
	for(int i=1;i<=scc;++i)
		ans=std::max(ans,dp[i]);
	printf("%lld",ans);
	return 0;
}